\chapter{Trabalhos Relacionados}\label{cap3}

Em Computação de Alto Desempenho é conhecido que, para um bom algoritmo paralelo executar, é preciso uma boa estratégia para a divisão da entrada e para a junção das várias soluções ao final. 

Há ainda a preocupação com a distribuição das tarefas entre os processadores, levando em conta que, ao final, todos eles devam ter realizado uma quantidade similar de processamento, evitando que alguns processadores fiquem ociosos enquanto outros estão sobrecarregados. Se isto acontecer, significa que a carga foi devidamente balanceada entre os processadores.

Neste capítulo, é apresentado o que se tem feito nos últimos anos na área de subdivisão de domínios para geração em paralelo de malha, mostrando as vantagens e desvantagens de cada técnica apresentada. Alguns trabalhos são tridimensionais, mas que podem ser adaptados para duas dimensões e por isso são mencionados neste capítulo.


\section{Decomposição Baseada na Distância/Volume/Centro de Massa}

Em \cite{bib:Pirzadeh09}, é descrita uma técnica baseada em Avanço de Fronteiras e Avanço de Camadas com decomposição contínua \textit{a priori}.

Inicialmente, é gerada uma malha de superfície nos pontos dados como entrada. Logo em seguida, é feita uma estimativa de carga nos subdomínios utilizando uma \textit{octree} que usa a informação da quantidade de faces para subdividir o domínio. Se necessário, serão criados planos de partições que dividem o domínio em regiões com cargas aproximadamente iguais. As posições destes planos são definidas através do centro de densidade da malha. Esse centro indica onde a massa efetiva do sistema está concentrada.

Em seguida, são identificadas as faces que interceptam o plano de partição e uma malha parcial é gerada na região do plano de corte. Depois disso, para cada lado da partição são agrupadas as faces dos novos subdomínios. Esse processo é repetido até que um número máximo de subdivisões tenha ocorrido. Ao final da execução, tem que ser realizada uma junção de todas as submalhas. A Figura~\ref{fig:pirzadeh09} ilustra os principais passos dessa técnica para o caso bidimensional.

 \begin{figure}[htbp]
     \centering
     \includegraphics[width=0.8\textwidth]{fig/pirzadeh09.jpg}
     \caption{Os principais passos da técnica de \cite{bib:Pirzadeh09} para gerar os segmentos de interface.}
     \label{fig:pirzadeh09}
 \end{figure}
 
Como vantagens pode-se citar que a utilização de avanço de camadas entre as partições faz com que a malha gerada seja praticamente idêntica a uma malha gerada sequencialmente, ou seja, não são gerados padrões entre as partições do domínio. Outra vantagem é que não é necessário nenhum pré-processamento custoso para definir ou construir as partições. Além disso, a construção da \textit{octree} para estimar a carga é automática e de baixo custo.

Uma das desvantagens desse método é que nem sempre é fácil gerar as malhas nas partições, especialmente em três dimensões. Além disso, a qualidade dessas malhas pode ser ruim, prejudicando assim a qualidade da malha gerada no modelo todo. Basear a quantidade de subdivisões num número máximo não é uma boa métrica para controlar a geração dos subdomínios quando não se tem uma boa estimativa de carga, isso pode gerar subdomínios em excesso, aumentando a comunicação entre os processos.

Em \cite{bib:Ivanov06}, foi desenvolvido um algoritmo baseado em Delaunay para geração de malhas tetraédricas em que o posicionamento do plano de corte é definido pelo centro de massa e pela matriz de inércia. O plano de corte é um plano perpendicular a um eixo que segue uma das três definições:

\begin{itemize}
  \item Planos criados são equidistantes;

  \item Volume entre os planos são iguais;

  \item Passa pelo centro de massa.
\end{itemize}

A escolha do critério utilizado para criar os subdomínios depende da geometria da entrada. Assim, dependendo da entrada, um critério pode ser melhor que outro, mas isso depende do conhecimento do usuário. Na Figura~\ref{fig:ivanov06}, as três formas de decomposição são apresentadas.

Após ter o plano de corte definido, é feita uma suavização da seção de corte e a sua triangulação para, posteriormente, serem geradas as malhas nos subdomínios. Um problema bem visível nesse método é que para se ter um bom plano de corte é preciso ter um modelo com uma geometria bem comportada, sem forma côncava, alongada ou afinada. Nesse trabalho a quantidade de subdomínios gerados é maior que a de processos para tentar melhorar o balanceamento dinâmico, uma vez que não se tem uma boa precisão na estimativa da carga.

 \begin{figure}[htbp]
     \centering
     \includegraphics[width=0.9\textwidth]{fig/ivanov06.jpg}
     \caption{As três formas de particionar. 1 - planos equidistantes. 2 - volume dos subdomínios iguais. 3 - centro de massa \cite{bib:Ivanov06}.}
     \label{fig:ivanov06}
 \end{figure}

Uma solução parecida é a apresentada em \cite{bib:Lammer00}, em que o plano de corte é traçado da mesma maneira, porém em duas dimensões, ou seja, um eixo de corte. Este eixo é usado para dividir o domínio recursivamente. A partir do eixo, uma aresta é formada, e os valores nos seus pontos extremos são interpolados dos valores dados como entrada. Quando o número de subdomínios for igual ao número de processadores, uma malha de Delaunay é gerada em cada interior concorrentemente. Essa técnica não apresenta uma boa escalabilidade nos seus resultados.


\section{Decomposição Baseada em Estruturas de Dados tipo Árvore} \label{sec:decomposição_est_dados}

Em \cite{bib:deCougny99}, a entrada do algoritmo é o contorno de um objeto. Cada processador fica com parte de uma \textit{octree} distribuída, que define planos de corte do domínio. A malha das células internas é gerada concorrentemente com \textit{templates}. A região entre o contorno e as células internas é preenchida por uma técnica de Avanço de Fronteira, onde são gerados os elementos internos a uma região delimitada pelos planos de corte. Por último é feita a conexão das malhas dos dois lados de cada plano e de suas intersecções. Essa técnica gera muitas partições, já que a cada subdivisão oito novos subdomínios são criados, e, por usar \textit{templates}, esta técnica pode gerar uma quantidade excessiva de elementos, além de possivelmente gerar elementos de qualidade ruim nas regiões próximas ao contorno.

Na técnica de \cite{bib:Lohner01}, é gerada uma \textit{octree} grosseira com relação ao contorno dado como entrada. Após essa geração, as células que contêm a parte da fronteira que gerará os menores elementos são identificadas. Assim, partes da malha, correspondentes a cada célula, são geradas simultaneamente por avanço de fronteira, de maneira que cada parte da malha gerada não possa cruzar as extremidades da célula que a contém. Cada octante sofre então um pequeno deslocamento na diagonal com o intuito de gerar mais elementos. Esse deslocamento elimina quase todas as faces entre duas ou mais células e diminui o tamanho da fronteira para o próximo passo. Desse modo a nova fronteira é encontrada e uma nova \textit{octree} é construída para ela, e o procedimento é repetido, até que não seja mais possível gerar malha. Na Figura \ref{fig:lohner}, são mostrados os passos do algoritmo e os deslocamentos que são realizados.


    \begin{figure}[!ht]
    \centering
    \subfloat[\textit{Octree} gerada para uma borda e passos do algoritmo (representação 2D, ou seja, uma \textit{quadtree}).]
    {\label{fig:lohner1}
     \begin{minipage}[c]{0.45\textwidth}{\includegraphics[width=\textwidth]{fig/lohner1.png}}\end{minipage}
    }
    \qquad
    \subfloat[Deslocamento da \textit{quadtree} para gerar mais malha (a linha escura é a fronteira).]
    {\label{fig:lohner2}
     \begin{minipage}[c]{0.45\textwidth}{\includegraphics[width=\textwidth]{fig/lohner2.png}}\end{minipage}
    }    
    \caption{Técnica de \cite{bib:Lohner01}.}
    \label{fig:lohner}
    \end{figure}

O deslocamento de cada octante é feito seguindo-se sempre o mesmo processo, e isso pode não ser o ideal para certos tipos de modelos, onde maneiras distintas de deslocamento poderiam ser mais eficientes (deslocamentos na diagonal, na direção dos eixos principais, entre outros).

Em \cite{bib:Larwood03}, é apresentada uma técnica de decomposição de domínio que tem como entrada uma triangulação de borda. Para saber quais subdomínios devem ser divididos, a técnica usa um critério baseado na quantidade de faces por subdomínio. A decomposição é feita recursivamente usando uma \textit{octree} caso seja tridimensional ou uma \textit{quadtree} caso seja bidimensional, verificando sempre se o número de faces de um subdomínio é menor do que o limite estipulado, e, enquanto a verificação for falsa, a decomposição ocorre. A quantidade máxima de subdivisões está limitada por uma constante maior que o número de processadores disponíveis. Isso evita a criação excessiva de partições e permite que um processador possa receber mais de uma tarefa ao longo da execução.

 \begin{figure}[htbp]
     \centering
     \includegraphics[width=0.8\textwidth]{fig/larwood03.jpg}
     \caption{Regiões de corte inválidas em cinza \cite{bib:Larwood03}.}
     \label{fig:larwood03}
 \end{figure}

Para evitar a criação de elementos ruins, é feita uma verificação no corte baseada no ângulo do vetor normal do plano de corte com a normal dos triângulos, de forma que o plano de corte não possa passar por triângulos com ângulo menor do que uma tolerância. Caso essa verificação falhe, a \textit{octree} (\textit{quadtree}, em 2D) sofre um deslocamento em um dos eixos. A Figura~\ref{fig:larwood03} mostra um exemplo onde alguns planos de corte falham nos testes. 
 
 \begin{figure}[htbp]
     \centering
     \includegraphics[width=0.9\textwidth]{fig/lo12_1.jpg}
     \caption{Pontos organizados em células. À esquerda por partição regular e à direita por \textit{kd-tree} \cite{bib:Lo12}.}
     \label{fig:lo12_1}
 \end{figure}

  Em \cite{bib:Lo12}, uma técnica bidimensional para uma triangulação de Delaunay por inserção de pontos é apresentada. Uma \textit{kd-tree} é utilizada para organizar os pontos da entrada em células. Estas células são agrupadas em zonas e distribuídas entre os processadores. A vantagem de usar uma \textit{kd-tree} é que cada célula tem uma quantidade de pontos aproximadamente igual e a busca espacial é facilitada na hora de fazer a inserção de pontos em uma região. A Figura~\ref{fig:lo12_1} mostra a organização de um conjunto de pontos por partição regular e por \textit{kd-tree}.
 
 A quantidade de subdomínios criados é compatível com a quantidade de processadores disponíveis, ou seja, cada processador terá que ficar responsável por uma zona. A inserção dos pontos em cada zona é feita em paralelo, sendo totalmente independente das outras zonas, e a malha gerada em cada zona também será independente.
 
 Os triângulos gerados nas bordas das zonas têm pontos de uma zona vizinha. Isso irá gerar uma camada a mais de triângulos nas zonas, que é necessário para obter uma malha sem buracos entre elas. Ao final, tem de ser feita a junção de todas as malhas geradas em uma só e, para isso, é preciso eliminar as redundâncias (triângulos repetidos entre duas zonas). Essa junção das malhas pode ser um processo complexo em determinados modelos e isso pode prejudicar o desempenho do algoritmo. A Figura~\ref{fig:lo12_2} mostra o fluxograma da triangulação em paralelo.
 
   \begin{figure}[htbp]
     \centering
     \includegraphics[width=1.0\textwidth]{fig/lo12_2.png}
     \caption{ Fluxograma da triangulação em paralelo \cite{bib:Lo12}.}
     \label{fig:lo12_2}
 \end{figure}

 O trabalho de \cite{bib:MFreitas13} apresenta uma técnica bidimensional que recebe como entrada uma fronteira e utiliza uma \textit{quadtree} para particionar e estimar a carga. As células folhas da \textit{quadtree} de particionamento são divididas entre os processadores disponíveis, onde são geradas as malhas internas. Depois de gerar as malhas nos subdomínios iniciais, a fronteira é atualizada e as células da \textit{quadtree} são deslocadas nos eixos cartesianos a 	fim de gerar mais malha. Esse processo de deslocamento e geração de malha é feito até que não seja mais possível gerar malha. Um processo mestre fica responsável por finalizar a geração da malha e fazer a melhoria na mesma. Este trabalho é classificado como contínuo \textit{a posteriori}. A Figura~\ref{fig:mfreitas} ilustra o passo de deslocamento da \textit{quadtree} no eixo X.
 
  \begin{figure}[htbp]
     \centering
     \includegraphics[width=0.4\textwidth]{fig/decomposition_quadtree_shift.png}
     \caption{ Malha gerada, espalhada entre os processos escravos, e as células da \textit{quadtree} de decomposição deslocadas para a direção +X \cite{bib:MFreitas13}.}
     \label{fig:mfreitas}
 \end{figure}
 
 
Em \cite{bib:RepMarkos13}, é apresentada uma evolução da técnica anterior que pode ser tanto bidimensional como tridimensional, por Avanço de Fronteira, com subdivisão baseada em BSP, que recebe como entrada uma superfície de faces triangulares ou uma lista de arestas, para o caso bidimensional. Inicialmente uma \textit{octree} é construída para estimar a carga no domínio de acordo com o tamanho das faces da superfície. As células internas da \textit{octree} têm o tamanho definido de acordo com a maior e a menor face da superfície de entrada. Uma BSP é utilizada para particionar o domínio de tal forma que a quantidade de subdomínios criados seja igual à quantidade de processadores disponíveis.

Após o particionamento, cada subdomínio pertencente a uma folha da árvore BSP gera sua malha por avanço de fronteira até que não seja mais possível avançar (quando chega no plano criado pela BSP), como mostra a Figura \ref{fig:passo_markos1}. Quando os dois filhos de um nó da BSP terminam de gerar a malha nos seus respectivos subdomínios, o nó pai fica encarregado de juntar as duas malhas e, se necessário, terminar a geração da malha no novo subdomínio criado pela junção dos dois filhos, como mostra as Figuras \ref{fig:passo_markos2}, \ref{fig:passo_markos3} e \ref{fig:passo_markos4}.

    \begin{figure}[h]
    \centering
    \subfloat[Malha gerada nas folhas da árvore da BSP.]
    {\label{fig:passo_markos1}
     \begin{minipage}[c]{0.35\textwidth}{\includegraphics[width=\textwidth]{fig/passo_markos1.png}}\end{minipage}
    }
    \qquad
    \subfloat[Junção e geração da malha no terceiro nível da árvore da BSP.]
    {\label{fig:passo_markos2}
     \begin{minipage}[c]{0.35\textwidth}{\includegraphics[width=\textwidth]{fig/passo_markos2.png}}\end{minipage}
    }
    
    \subfloat[Junção e geração da malha no segundo nível da árvore da BSP.]
    {\label{fig:passo_markos3}
     \begin{minipage}[c]{0.35\textwidth}{\includegraphics[width=\textwidth]{fig/passo_markos3.png}}\end{minipage}
    }    
    \qquad
    \subfloat[Malha final utilizando particionamento baseado em BSP.]
    {\label{fig:passo_markos4}
     \begin{minipage}[c]{0.35\textwidth}{\includegraphics[width=\textwidth]{fig/passo_markos4.png}}\end{minipage}
    }
    \caption{Passos da geração da malha no trabalho de \cite{bib:RepMarkos13}. Cada cor representa a malha gerada por um processador.}
    \label{fig:tecnica Markos 2013}
    \end{figure}

    
A grande vantagem dessa técnica está na utilização da BSP, que acaba permitindo a geração de subdomínios com cargas mais equilibradas e no ganho de velocidade ao se evitar os deslocamentos que aconteciam anteriormente. Por essa abordagem necessitar de uma sincronização e junção da malha em cada nível da BSP, há uma perda na velocidade apesar dessas junções serem feitas em paralelo por processos diferentes.
    

\section{Decomposição Baseada no Eixo Mediano}

O eixo mediano é uma maneira de descrever a forma de um objeto, e pode ser utilizado para garantir uma decomposição de domínio com separadores que formam bons ângulos com as bordas dos modelos.

Em \cite{bib:Leonidas06}, é apresentada uma técnica bidimensional que utiliza a triangulação de Delaunay por divisão e conquista para um conjunto de pontos dados como entrada. Primeiramente, é feita uma triangulação utilizando apenas os pontos da borda, que é utilizada para a geração de um grafo ponderado, onde o peso de uma aresta é igual ao raio da circunferência circunscrita do triângulo que a contém. Em seguida é feita uma contração desse grafo, onde os vértices do grafo representam a área a ser triangularizada (futuros subdomínios), e as arestas representam a conexão entre essas áreas.
 

 \begin{figure}[htbp]
     \centering
     \includegraphics[width=0.9\textwidth]{fig/leonidas06.jpg}
     \caption{Partições em 2, 4, 8 e 16 \cite{bib:Leonidas06}.}
     \label{fig:leonidas06}
 \end{figure}

Através do grafo formado, os planos de corte são posicionados e os subdomínios formados. A Figura~\ref{fig:leonidas06} mostra o resultado de decomposições para quantidades diferentes de subdomínios. Esse processo de subdivisão ocorre até que a quantidade de subdomínios criados seja suficientemente grande. Isso acontece para tentar melhorar o balanceamento de carga. Após isso, a geração da malha interna poderá ser realizada. A desvantagem dessa técnica é a ausência de uma estimativa de carga eficiente, precisando gerar vários subdomínios para melhorar o balanceamento de carga.

 \begin{figure}[htbp]
     \centering
     \includegraphics[width=0.8\textwidth]{fig/glut08_1.jpg}
     \caption{Passos da técnica baseada na malha de superfície. (a) malha de superfície; (b) corte; (c) seção transversal; (d) malha final \cite{bib:Glut08}.}
     \label{fig:glut08_1}
 \end{figure}

\section{Decomposição Baseada em \textit{Bounding Box}}

Em \cite{bib:Glut08}, é apresentada uma técnica para malhas tridimensionais com uma abordagem baseada na decomposição geométrica onde a entrada é uma malha de superfície. Nesse trabalho são descritas duas técnicas baseadas na \textit{bounding box} gerada a partir da entrada.

A seleção do separador do domínio deve garantir um custo de corte baixo, ou seja, encontrar e posicionar o plano de corte não pode ter um custo computacional alto. Além disso, deve garantir um bom balanceamento de carga e minimizar os elementos conectados por múltiplos subdomínios.

A primeira técnica é baseada na malha de superfície. Para o plano de corte ser criado, é preciso a localização do contorno da malha de superfície e do separador. O contorno é então projetado no separador usando uma função 2D de controle espacial baseada no tamanho das arestas (Figura~\ref{fig:glut08_1}).

 \begin{figure}[!ht]
     \centering
     \includegraphics[width=0.8\textwidth]{fig/glut08_2.jpg}
     \caption{Passos da técnica baseada na malha volumétrica grosseira. (a) malha volumétrica grosseira; (b) refinamento da seção transversal; (c) seção transversal; (d) malha final \cite{bib:Glut08}.}
     \label{fig:glut08_2}
 \end{figure}

A segunda técnica se baseia numa malha volumétrica grosseira. Primeiramente, é feita a geração de uma malha 3D grosseira utilizando alguma função de controle espacial. O posicionamento do plano de corte é feito parecido com a técnica anterior, porém utilizando a malha volumétrica como função espacial (Figura~\ref{fig:glut08_2}).

Essa técnica depende muito da geometria da entrada já que são utilizadas informações da \textit{bounding box} dessa entrada. Isso afeta diretamente a criação dos planos de corte, e por consequência, a malha gerada ao final.

\section{Considerações Finais}

As técnicas que foram discutidas neste capítulo apresentam bons resultados, mas o balanceamento de carga pode ser um problema em muitas delas, fazendo o desempenho do algoritmo paralelo cair. A forma com que os cortes são posicionados nessas técnicas dependem bastante do formato do objeto de entrada. Além disso, algumas técnicas necessitam de intervenção de um usuário, ou seja, o processo de geração da malha não é totalmente automático. Uma boa abordagem de balanceamento e de decomposição de domínio é essencial para algoritmos de subdivisão de domínios, caso contrário, o tempo para geração de malha pode ser prejudicado e a qualidade da malha ser afetada.
